475. 供暖器

Similar Question

leading to the advanced question

Solution Tips

方案一: 双指针

var findRadius = function(houses, heaters) {
    // 所有的加热器中, 离加热器最远的房屋的距离就是最小半径
    // 从左到右遍历, 先找到第一个加热器, 在这个加热器左边的所有房屋都只能靠它一个人加热
    // 从右到左遍历, 找到最后一个加热器, 所有的在其右边的房屋都只能靠它一个人加热
    // 这样能确定最小的加热半径, 起码得有这么多
    // 然后再重新遍历一遍, 去找每一个房屋, 离他最近的加热器有多远, 找到一个房屋, 就去找对应的加热器
    // 暴力法就是这样做了, 但是每次查找存在重复
    // 比如我在1查到, 离他最近的加热器是 5, 那么对于2来说, 最近的加热器就是 5 - 1 的距离, 是不需要重新遍历加热器数组的, 这个前提是 house[i + 1] < heat[i]
    // 在确定了 1 需要 5 的加热器之后, 半径就是 4 了, 所以可以直接跳到 9 号房屋, 而且我们知道有一个加热器离他的距离为4, 所以继续往后找看看下一个加热器在哪里, 如果距离小于4, 就用新的加热器, 如果距离大于 4, 那么让旧的加热器增大或者让新的加热器变成4都是一样的, 具体就看哪个更近
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0, j = 0; i < houses.length; i++) {
        let curDistance = Math.abs(houses[i] - heaters[j]);
        while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
            j++;
            curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
        }
        ans = Math.max(ans, curDistance);
    }
    return ans;
};